import bisect
from typing import List


class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = []
        nums = [envelope[1] for envelope in envelopes]
        for num in nums:
            index = bisect.bisect_left(dp, num)
            if index >= len(dp):
                dp.append(num)
            else:
                dp[index] = num
        return len(dp)


if __name__ == '__main__':
    s = Solution()
    r = s.maxEnvelopes([[4, 5], [4, 6], [6, 7], [2, 3], [1, 1], [1, 1]])
    print(r)
